\chapter{新型混合末级缓存FuseLLC}\label{chap:fusellc}
{

\section{引言}
本文于第三章内设计了一个高性能的末级缓存并采用多种手段对其在重内存负载下的性能进行了优化，然而片上缓存的容量有限，一般只能达到16MB或32MB的大小，当负载的工作集大小超过缓存容量时片上缓存对其性能优化幅度不明显。因此，想要继续提升处理器的访存性能，需要探索新的方向。

混合内存是被认为能够进一步提升处理器访存性能的一种技术，混合内存通过将高速低容量的内存与慢速高容量的内存结合，并试图将频繁访问的数据存储到快内存的部分，从而同时获得高速度与高容量的优点。

然而，混合内存技术存在着一个关键问题，那就是其元数据访问开销巨大。在访问混合内存时，首先需要从基于DRAM的快内存中读取元数据，这相当于增加了一次额外的访存行为，使得混合内存访问效率降低。

在处理器的访存层次结构中，LLC与混合内存之间存在着两个重要的性质。首先，LLC与混合内存处于相邻的逻辑层次结构，LLC发出的数据重填请求将直接与混合内存进行交互。其次，LLC与混合内存呈一定的互补性，当程序的工作集小于LLC的大小时，此时主要的访存请求由LLC完成，而遇到重内存负载的程序时，访存请求主要由混合内存进行完成。此外，LLC本身也有一个独特的性质，即LLC是处理器片上拥有最大存储容量的组件。

片上末级缓存的这几个重要性质表明，存在动态复用片上末级缓存的空间，从而加速混合内存元数据访问的可能性。

\section{新型混合末级缓存FuseLLC整体设计}

本章提出了FuseLLC新型混合末级缓存，这是一个末级缓存与混合内存技术相结合的缓存系统。FuseLLC通过对片上LLC的空间进行动态的划分与重用，以加速混合内存元数据的访问，从而进一步提升处理器的访存性能。通过复用片上末级缓存的空间，FuseLLC能获取到比前人工作更多的片上SRAM空间供混合内存使用，并且仅需要少量用于管理的额外硬件开销。在结构设计上，FuseLLC对LLC与混合内存的内部设计改动较小，避免了设计之间紧耦合而限制了设计空间的问题。

FuseLLC在设计与实验时，认为混合内存部分采用的是DRAM Cache（简称DC）的方案，但是其原理也同样适用于混合内存中PoM的设计方案。



图\ref{fig:FuseLLC_OverView}展示了FuseLLC的整体设计，其中的箭头表示FuseLLC进行缓存访问的流程（省略了重填的步骤）。

在该系统中，慢内存部分为NVM，作为主存使用，而快内存部分为DRAM，用做NVM的缓存。为了保持传统缓存结构中的称呼不变，本文仍然将CPU片上缓存的最后一级称为LLC。在LLC与DC外，本文还引入了一个特殊的阵列称为MPtr Array，专门用于辅助索引DRAM缓存的元数据。本文将LLC与MPtr Array组成的复合模块称为FuseLLC。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_OverView}
    \bicaption{\enspace FuseLLC整体设计}{\enspace FuseLLC Overview}
    \label{fig:FuseLLC_OverView}
\end{figure}

FuseLLC的整体访问流程为：
\begin{itemize}
    \item 当CPU向FuseLLC发出一个请求时，首先会在LLC的标签阵列中查找，如果发现命中，则与正常的LLC一样，从LLC的数据阵列中读出对应数据并返回给CPU。
    \item 若LLC查找时发现未命中，则会在MPtr Array中进行查找，如果发现在其中命中，则会获取对应的MPtr，即DC元数据指针，然后根据MPtr去索引LLC中存放的DC元数据。否则需要进行一次DC的访问来获取元数据。
    \item 接着，在DC元数据中进行比对，以确定数据是否于DC中命中，如果命中，则会访问DC以获取数据，否则需要从NVM主存中获取数据。

\end{itemize}

在DRAM缓存的部分，本文参考了先前研究者的方案，选用了7路组相连的方案，该方案可以在保证标签与数据处于同一DRAM行的同时，保证一个组内所有的元数据大小总和不超过64B，因此可以一次访问便取回所有元数据，同时允许一个组内的元数据放在LLC的数据块内。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_DC}
    \bicaption{\enspace DRAM缓存的设计}{\enspace DRAM Cache Design}
    \label{fig:FuseLLC_DC}
\end{figure}

\section{基于MPtrArray的混合数据管理方法}

想要将LLC与DRAM Cache融合成为混合末级缓存，面临着三个挑战：

\begin{enumerate}

\item 混合末级缓存意味着LLC会同时存放着普通的LLC数据和DC元数据，需要有一个方法来标识和管理不同的数据类型。

\item LLC的数据与DC元数据大小不相同，但是受到物理设计的制约，在混合末级缓存中他们必须共享相同的物理存储单元。一个LLC行可存储的数据一般为64B，如果这个大小不能适应DC的元数据大小，那么会造成空间利用率或者访问效率的低下。

\item 同时，由于DC的容量更大，其往往拥有更多的组以及更大的缓存块容量，这就造成了在使用物理地址去访问LLC和DC时，其索引方式不同。当LLC与DC分离时，只需要在访问这两者时采用不同的索引方式即可。但是当LLC与DC融合后，需要在LLC的数据阵列中以两种不同的索引去索引不同的数据。

\end{enumerate}




前两个问题相对比较容易解决。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.6\textwidth]{FuseLLC_MetaLine}
    \bicaption{\enspace FuseLLC中标记与存储DC元数据}{\enspace Tagging and Storing DC Metadata in FuseLLC}
    \label{fig:FuseLLC_MetaLine}
\end{figure}



对于如何标记不同数据类型的问题，FuseLLC在LLC的标签部分引入一个新的标志位M，该位置高表示此时对应的数据并不是普通的LLC数据，而是存放着DC的元数据。该位的引入解决了在普通LLC请求查找时如何区分普通的LLC行与元数据行的问题。



对于混合末级缓存中同时存在的普通LLC数据以及DC元数据的问题，本文在DRAM缓存的结构上采用了与LLC相适配的设计方案。在DRAM缓存的设计上选用了7路组相连的设置，这个设置的好处是一个组中的所有元数据总和刚好不超过LLC的缓存行大小。在LLC对DRAM缓存元数据进行缓存时，数据行内存放的就是一整个DC组的元数据。在通过DC组索引到了对应的LLC数据行内，在这一行内进行比较即可知道DC是否命中。


\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{FuseLLC_CACHE_ADDR}
    \bicaption{\enspace LLC与DRAM缓存对地址的不同划分方式}{\enspace Different Partitioning Methods of Addresses between LLC and DRAM Cache}
    \label{fig:FuseLLC_CACHE_ADDR}
\end{figure}

但是第三个问题相对而言比较棘手。假设CPU物理地址为48位，LLC大小为16MB，采用16路组相连，块大小为64B，而DC采用的是总容量2GB，7路组相连，块大小为512B的设计。那么CPU在进行LLC访问和DRAM缓存访问的时候地址的划分如图\ref{fig:FuseLLC_CACHE_ADDR}所示。从图中可以看出，在访问LLC与DRAM缓存时，两者的索引方式完全不同，但是在混合末级缓存的设计中，硬件需要在相同的物理存储单元上同时进行两种不同的索引方式，这给设计带来了挑战。

因此本文提出了MPtrArray这一数据管理模块，它通过两段式查找法，实现了LLC与DC两种不同索引方式之间的转换，同时使得LLC与DC的物理设计参数（如路数，组大小等）解耦合。

MPtrArray是一个N路组相连的数据结构，其中路数N与组的数量均可任意设置，与LLC和DC的设计完全解耦合。但是组数量一般设置为LLC组数量的1/4或者1/8以获得更好的灵活性，详见第\ref{FuseLLC_swap}小节。MPtrArray内部分为两个部分，一个是SetTag，另一个是MPtr。

在FuseLLC进行DC元数据的查找时会分为两步。

第一步会从物理地址中截取出DC组索引的低位作为MPA-Set，用于索引MPtrArray，接着比对MPtrArray内的SetTag，如果命中则代表MPtr有效。随后将MPtr的高位部分，即MPtr-Set与MPA-Set合并，得到了LLC组号，并通过截取MPtr的低位部分得到LLC的路号。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_LookUp_1}
    \bicaption{\enspace FuseLLC中进行DC元数据查找的第一步}{\enspace The First Step in DC Metadata Lookup at FuseLLC}
    \label{fig:FuseLLC_LookUp_1}
\end{figure}

第二步则是通过第一步中得到的LLC组和LLC的路号索引LLC Data Array中的对应行，该行中的数据即为对应DC组的元数据。索引到DC元数据所在行后，会使用物理地址高位中的DC Tag来与LLC中存放的DC元数据进行比较，从而得知是DC元数据否命中。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_LookUp_2}
    \bicaption{\enspace FuseLLC中进行DC元数据查找的第二步}{\enspace The Second Step in DC Metadata Lookup at FuseLLC}
    \label{fig:FuseLLC_LookUp_2}
\end{figure}


通过引入了MPtrArray，成功地实现将两种不同的数据统一存放在LLC内的功能，解决了LLC与DC地址索引的差异问题。同时，MPtrArray赋与了混合末级缓存强大的解耦合能力，使得在设计混合末级缓存部分的参数时，不需要受到LLC与DC物理参数的限制。这些优点使得对FuseLLC的进一步优化，如动态调整划分比例，更自由的数据布局成为了可能。

\section{基于多点采样的全局动态缓存路划分}
为了能够适应不同的负载，FuseLLC需要一种能动态对LLC进行划分的方案，即决定LLC的容量有多少可用于LLC正常的存储，有多少可用于DC元数据的存储。对于一个缓存划分方案而言，其可以分为两个部分，分别是划分比例的获取，以及划分比例的控制。

首先来讨论对于划分比例的控制。常见的缓存划分比例控制有两种方案，第一种是基于路的划分方案\citep{Qureshi_Patt_2006}\citep{Kim_Chandra_Solihin_2004}\citep{ElSayed2018KPartAH}，这个划分方案的优点是可以实现很清晰的划分，并且实现相对简单。但是基于路的划分，其划分的粒度取决于缓存中的路数，比如一个16路组相连的缓存只能以1/16的缓存容量粒度进行调整，同时路划分属于硬划分，在一些局部环境下可能不能适应局部的数据分布。而第二种方案则是通过修改替换算法或者插入算法，以概率\citep{Xie2009PIPPPP}\citep{Manikantan2012ProbabilisticSC}的方法来实现对整体数据分布的软控制。但是这一种方案不适用于混合末级缓存，因为混合末级缓存中LLC与DC无论是缓存块大小，还是访问模式，都有较大的差异，难以通过统一的算法进行管理。

因此，在FuseLLC中的设计中，本文创新性地提出了新型的混合划分方案，在全局使用了基于路的硬划分方案，但是在局部上允许使用软划分方案来缓解冲突问题。本章节首先介绍全局的划分方式。

FuseLLC中用于管理LLC中DC元数据的结构是MPtrArray，这本质上是一个数据存放位置的指针阵列，因此只要控制MPtrArray的可用的大小，即可控制LLC的划分比例。为了与\ref{FuseLLC_swap}章节中的局部软划分方案协同工作，FuseLLC在全局的划分中采用的是单向的路数硬上限方案。FuseLLC在全局引入一个可变的上限MPtrWayLimit，在MPtrArray的所有组中，均不能使用超过MPtrWayLimit数量的路，但是允许使用低于这个数量的路。

使用全局路划分的方案使得FuseLLC可以很方便地调节上限，为划分比例控制算法带来了便利。但是路划分的划分颗粒度过粗的问题依然存在，因此，本文利用了MPtrArray的特性来优化这一问题。

由于MPtrArray可以实现对LLC的组数和路数解耦合，因此在设计中可以将MPtrArray的组数量设置为LLC的组数量的1/4或1/8，这等效缩小了在进行路划分时改变一路产生的容量变化。假设系统拥有一个16MB容量16路的LLC，在原始的LLC上采用路划分的方案，其划分调整的粒度为1MB，这个划分调整粒度过粗。而如果在一个组数量为LLC组数量1/4的MPtrArray上进行路划分，那么划分调整的粒度就变为了256KB，划分的精细度有了明显的改善。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{FuseLLC_update_limit}
    \bicaption{\enspace FuseLLC采样并更新划分上限示意图}{\enspace 
    FuseLLC Sampling and Updating Partition Upper Limit Schematic}
    \label{fig:FuseLLC_update_limit}
\end{figure}

接着是划分比例的获取部分。本文参考了Set Dueling\citep{Qureshi_Jaleel_Patt_Steely_Emer_2008}和梯度下降的思想，同时扩展了平均访问延迟公式以估计最优的划分比例。如图\ref{fig:FuseLLC_update_limit}所示，在系统运行时，FuseLLC会将LLC中所有的组分为非采样集与若干个采样集，每个采样集内包含若干个组，例如一个采样集包含32个LLC组。不同的采样集内有着不同的划分路上限，如非采样集内的划分上限MPtrWayLimit为K路，设置了4个采样集，那么一个可能的采样集内划分上限为K-2，K-1，K+1，K+2。每隔一定的时间间隔，FuseLLC会收集所有采样点内的命中率信息，同时应用扩展的平均访问延迟公式(公式\ref{eq:fusellc_lat})计算出各采样点内的平均访问开销。这样一来，便可预估出最佳划分比例应当调整的方向，并进行动态的调整。

\begin{equation}
DCLat = FMLat \times DCHR + SMLat \times (1 - DCHR)
\end{equation}
\begin{equation}
MetaLat = MHLat + FMLat \times (1 - MHRate)
\end{equation}
\begin{equation}\label{eq:fusellc_lat}
FLLCLat = LLCHLat + (MetaLat + DCLat) \times (1 - LLCHR)
\end{equation}


\section{基于群的局部争抢避让机制}\label{FuseLLC_swap}

许多研究表明，缓存的访问有非常不均匀的性质\citep{Abella_González_2006}\citep{Davanam_Lee_2010}，在某些组中的请求频繁程度要高于其他组，从而导致出现频繁的冲突问题，因此现代处理器中常常使用哈希函数或SkewHash\citep{Seznec_Bodin_1993}\citep{Takayashiki_Sato_Komatsu_Kobayashi_2019}等方式来来试图缓解该影响。但是这些方法只能对数据局部热点问题进行缓解，而不能彻底避免。

在FuseLLC中，由于LLC与DC的数据进行了混合存储，而这两者都会有各自的热点，这两者之间的热点之间难免会出现冲突的情况，此时会导致一种新的冲突出现。例如，在热点组内存放着DC元数据，如果允许LLC将其替换，那么DC元数据会很快被换出从而损失性能，如果不允许LLC将其换出，那么LLC可用路会减少，该热点组内的LLC性能会出现明显下降。

因此，在FuseLLC的设计中的一个关键考量就是如何减轻LLC部分的数据与DC元数据相冲突时的性能损失。本文为此提出了局部争抢避让机制。该机制采用了两种方法来降低和缓解冲突：

\begin{enumerate}
    \item 通过增大MPtrArray的关联度来降低DC元数据出现局部冲突的概率。
    \item 通过允许LLC与DC元数据冲突时，DC元数据交换到其他LLC组内，从而对冲突进行避让。
\end{enumerate}

在缓存中出现局部冲突的原因是多个频繁访问的内存地址被映射到了缓存的同一个组中，而缓存的关联度不够同时容纳所有的频繁访问数据，因此在访问过程中数据会被不断地换入换出，因此导致了局部的冲突问题。而许多研究者指出，缓存的关联度取决于其替换的时候可选的换出元素的数量。因此优化的第一步就是通过增加DC元数据可替换的位置，从而增加其关联度，进而减少其局部冲突的可能性。


FuseLLC在MPtrArray中将MPtr指针分为两部分，低位用于索引LLC的路号，而高位参与索引LLC的组号。例如，在设计中把高位的宽度设置为2位，这样一个MPtr可以指向4个可能的LLC组之一，本文中将这4个组称为一个群(Group)。在16路的LLC中，经过该修改，DC元数据可插入的位置即变为了64路，降低了DC元数据自身出现冲突的概率。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{FuseLLC_Swap}
    \bicaption{\enspace FuseLLC的冲突避让过程}{\enspace 
    Fusellc's Conflict Avoidance Process}
    \label{fig:FuseLLC_Swap}
\end{figure}

同时，由于LLC的同一个内存地址只能在同一个组的16路中选择位置插入，而DC元数据可以在4个组的总共64路中选择位置进行插入，因此FuseLLC可以让DC元数据在被LLC数据替换时，不是直接逐出缓存，而是调换到其他的LLC组中，通过转移DC元数据的位置，从而实现了与LLC的冲突避让。



具体而言，以Group大小为4，LLC的组数为1024为例。FuseLLC首先会将LLC的组分成4份，如分成0至255，256至511，512至767，768至1023这4个部分。然后将这4个部分中对应的组号进行匹配，形成一个Group，这样可以尽力避免一个Group内出现多个热点。如0,256，512，768这4个组划分为一Group。假设256这一个组是LLC的热点区域，里面发生频繁的LLC重填，在某一次重填中将要替换掉一个存放其中的DC元数据，那么此时FuseLLC将在这一个Group内寻找一个较冷的组，并将这个DC元数据移至这个冷的组内。只有当一个Group内没有冷的组才会允许逐出DC元数据。


\section{LLC冷热区域识别算法}\label{FuseLLC_majorminor}

在FuseLLC进行冲突避让的过程中，一个重要的问题就是如何识别一个Group中哪些是冷的LLC组，哪些是热的LLC组。这一个问题可以抽象为一个替换算法的问题。但是传统的替换算法，如LRU，SRRIP\citep{Jaleel_Theobald_Steely_Emer_2010}等算法是为了一个组内的多个路之间的替换操作而设计的。每一个路，实际上对应着一个缓存块，缓存块大小通常较小，访问次数和频率也较小，并且当缓存块被逐出并被新的缓存块取代后，计数器信息将会重置。

而FuseLLC中需要面临的是多个组之间的替换算法问题，每一个组包含有若干路，因此其访问频率和次数都是单个路的数倍。同时组不存在被逐出的情况，所以计数器信息会持续地更新而不会被重置。因此，传统的缓存替换算法并不适用于该场景。

由于FuseLLC想通过替换算法获得的是几个组之间在一段时间内的冷热情况，即访问的次数，因此在设计时需要的是基于访问频率的替换算法，而不是象LRU那样的基于最近访问的替换算法。但是由于每个组访问次数都很多，并且热的组和冷的组甚至普通组之间都存在着巨大的访问次数差异，因此会给替换算法带来两个问题：

\begin{enumerate}
\item 计数器的值会很快饱和。由于硬件资源有限，计数器所能记录的最大值也有限，而替换算法又需要持续记录组访问情况，因此计数器很快就会变为饱和状态。
\item 热点组可能会使得其他组计数器迅速老化。为了能在有限大小的计数器上持续记录访问状态，需要设计老化算法以减少不常用计数器的值，但是由于热组和普通组之间访问次数差异过大，很容易出现热组的计数器值饱和，而其他组计数器值全被老化为0的情况，使得难以对普通组和较冷的组状态进行区分。

\end{enumerate}

因此本文提出了一种创新性的替换算法，用于识别LLC组之间的冷热情况，称之为Major-Minor算法。该算法为每个组维护了一个访问次数相关的计数器，通过限制计数器较高时计数器的增长概率来避免计数器过快饱和的问题，同时也能规避其他计数器过快老化的问题。

以一个具体的例子说明该算法的操作步骤。首先硬件为每一个组维护一个计数器，以位宽为6的计数器为例，即计数区间为0-63，所有的计数器初始化为0。接着取一个常数F，例如F=16，每当一个组进行访问时，假设当前该组对应的计数器值为$C_i$，此时硬件需要生成一个0-63之间的随机数R，以及计算出$T_i$（公式\ref{eq:fusellc_threshold}）。接着比较$T_i$与计数器值$C_i$的大小，若$C_i$大于等于$T_i$，则允许计数器值增加1。增加完毕后，检查计数器是否已达到饱和，如果已达到饱和，那么将所有计数器的值减1（算法\ref{alg:update_major}）。

在判定是否为热点与冷点时（算法\ref{alg:get_set_type}），算法需要设置两个阈值，如$L_{minor}=16$和$L_{major}=59$，如果一个组对应的计数器值小于$L_{minor}$，那么算法认为这是一个冷的组，如果大于$L_{major}$，那么算法认为这是一个热点区域。

在算法的执行过程中，硬件生成随机数可以采用LSFR以低开销生成伪随机数，而选择合理的常数$F$可以使得计算$T_i$时仅需要移位和加减操作，不需要高开销的乘法操作。因此整个算法在硬件上的开销属于轻量级，可以被真实硬件所实现。

\begin{equation}\label{eq:fusellc_threshold}
    T_i = C_i \times  \frac{F-1}{F}
\end{equation}

\begin{algorithm}
    \caption{更新计数器算法}
    \label{alg:update_major}
    \begin{algorithmic}[1]
    \Procedure{UpdateCnt}{$groupIdx$,$set$}
        \State $F \gets 16$
        \State $MAX\_CNT \gets 63$
        \State $rand\_num \gets \Call{Random}{0,MAX\_CNT}$
        \State $C \gets \Call{GetCntArray}{groupIdx}$
        \State /*C是该Group对应的计数器数组*/
        \State $T \gets C[set] * (F - 1)/F$

        \If{$rand\_num \geq T$}
            \State $C[set]+=1$
        \EndIf

        \If{$C[set] \geq MAX\_CNT$}
            \For{$i \gets 0$ \textbf{to} $SETS\_IN\_GROUP$}
                \State $C[i]-=1$
            \EndFor
        \EndIf
    \EndProcedure
    \end{algorithmic}
\end{algorithm}

\begin{algorithm}
    \caption{热点冷点判别算法}
    \label{alg:get_set_type}
    \begin{algorithmic}[1]
    \Procedure{GetSetType}{$groupIdx$,$set$}
    \State $C \gets \Call{GetCntArray}{groupIdx}$
    \State $MAJOR\_THRESHOLD \gets MAX\_CNT - 4$
    \State $MINOR\_THRESHOLD \gets 16$

    \If{$C[set] < MINOR\_THRESHOLD$}
        \State \Return $IS\_MINOR$
    \ElsIf{$C[set] > MINOR\_THRESHOLD$}
        \State \Return $IS\_MAJOR$
    \Else
        \State \Return $IS\_NORMAL$
    \EndIf
    \EndProcedure
    \end{algorithmic}
\end{algorithm}

该算法之所以有效，是因为它对计数器的增长与老化进行了控制。假设只有单个计数器的访问的情况下，以计数器位宽6，常数F=16为例对单个计数器的增长情况进行模拟并画出图\ref{fig:FuseLLC_Major_Sim}。从图中可以看到，在计数器的值较低时，计数器以近乎线性的速度进行增长，而随着计数器逼近饱和，其计数器值的增长变得逾发缓慢。这特性带来了几个好处：

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{FuseLLC_Major_Sim_bw}
    \bicaption{\enspace Major-Minor算法计数器增长的模拟}{\enspace Simulation of Major-Minor Algorithm Counter Increment}
    \label{fig:FuseLLC_Major_Sim}
\end{figure}

\begin{itemize}

\item 第一个好处是减少压缩了计数器所需的物理资源，单个计数器饱和前的访问次数增加了一倍有余。本文称饱和的计数器试图继续增加为一次“溢出”，饱和后的计数器平均十余次访问才会产生一次溢出。而在实际设计中，一个计数器发生溢出会造成所有计数器共同减1，也就是进行一次“老化”操作，因此老化的频率也会大大下降，避免了组之间访问次数差异过大而导致大部分计数器被老化为0的问题。

\item 第二个好处是可以保持访问频率高与频率中等的组的区分度。假设系统有两个组，分别是A和B，在一定时间内分别访问了150次和80次，则这两个组对应的计数器分别约为60和50，均仍然处于0-63的计数器范围内，且能区分出这两个组的访问频率。而以线性方式增长的计数器则会使得AB均发生溢出情况，无法区分哪个组有更高的访问频率。

\item 第三个好处是，计数器低数值段的线性增长区间有利于区分真正的冷组。该算法的控制下，老化的发生频率已经大幅度下降，同时当一个计数器被老化成一个较低的值时，再次访问该组时，计数器会以较快的速度增长。因此当发现一个组的计数器处于较低值时，需要同时满足存在另一频繁访问的组，且该组访问次数极少这两个条件。此时硬件便有了充分的证据认为这是一个可用的冷组。

\end{itemize}



\section{实验评估}
\subsection{实验设置}

\textbf{模拟器参数设置}
本文使用了zsim模拟器\citep{Sanchez_Kozyrakis_2013}来作为FuseLLC的实验评估平台，这是一款基于Pin的模拟器。本文在zsim上，构建了一个8核的乱序执行CPU，其拥有16MB容量的LLC，使用2GB容量的DDR4作为快速内存，以及使用32GB容量的NVM作为慢速内存。当LLC部分缺失后，访问MPtrArray的延迟为5个CPU时钟周期，这是一个相对保守的设计，在实际物理设计中将MSHR阵列与SRAM放置更近可以获得更低的延迟。

% Please add the following required packages to your document preamble:
% \usepackage{booktabs}
\begin{table}[!htbp]
    \bicaption{\enspace 系统参数设置表}{\enspace System Configuration Table}
    \label{tab:sys_conf}
    \centering
    \begin{tabular}{@{}l|l@{}}
    \toprule
    模块        & 配置                              \\ \midrule
    CPU核      & 8核，3.2GHz，x86-64，乱序执行          \\
    L1-I/D 缓存 & 每核32KB私有缓存，64B块大小，4路组相连，LRU替换算法 \\
    L2 缓存     & 每核1MB私有缓存，64B块大小，8路组相连，LRU替换算法  \\
    LLC       & 16MB共享缓存，64B块大小，16路组相连，LRU替换算法  \\ \midrule
    MPtrArray & 16路组相连，5周期访问延迟，占用空间开销约112KB。     \\ \midrule
    快内存 & \begin{tabular}[c]{@{}l@{}}DDR4-3200, 4 channels, 2 ranks, 16 banks;\\ RCD-CAS-RP: 22-22-22; 2GB;\end{tabular}             \\ \midrule
    慢内存 & \begin{tabular}[c]{@{}l@{}}NVM, 1333 MHz, 4 channels, 1 rank, 8 banks;\\ read 76.92 ns; write 230.77 ns; 32GB;\end{tabular} \\ \bottomrule
    \end{tabular}
\end{table}



在DRAM缓存的部分，测试参数参考了Unison Cache\citep{Unison_cache_2014}以及其他论文\citep{Jevdjic_Volos_Falsafi_2013}\citep{Ryoo_Meswani_Prodromou_John_2017}中的方案，选用了512B的缓存块大小，同时在缓存的组织方式上，本文参考了Morphable DRAM Cache\citep{Cha_Kim_Park_Huh_2019}中的7路组相连设计。这样的设计可以使得FuseLLC的DRAM缓存访问更为高效。模拟器中系统的具体配置见表\ref{tab:sys_conf}。

\textbf{FuseLLC开销分析}

FuseLLC硬件上的开销主要来自两部分，分别是MPtrArray以及对每一个LLC组采用Major-Minor算法时的计数器开销。

在单个MPtrArray的项中，SetTag大小为7 Bits，MPtr为6 Bits，有效位与脏位分别占用1 Bit，即单个MptrArray项大小为14 Bits。MPtrArray有4K个组，每组有16路，则MPtrArray总开销为112KB。

在Major-Minor算法中，需要为每个LLC的组维护一个6 Bit的计数器，而LLC总共有16K个组，因此总开销为96KBits，即12KB。

FuseLLC其余的开销则是各类用于统计延迟的计数器，每个计数器大小为64Bit，即8B。总共需要的各类计数器个数根据采样点设置的不同，在10~20之间，因此计数器部分的开销在0.2KB以内，为了方便计算，计为1KB。

因此，总的FuseLLC开销约为125KB。

\textbf{基线模型设置}

由于FuseLLC的创新点主要集中于对DC元数据的缓存上，因此在对比实验中DRAM缓存部分保持不变。而在DC元数据缓存部分，测试用的基线模型参考了ATCache\citep{Huang_Nagarajan_2014}和Fazal Hameed\citep{Hameed_Bauer_Henkel_2013}等人的工作，他们均在LLC与DC之外引入了一片单独的SRAM作为DC元数据的缓存，并且这两个工作中提出的缓存的组织结构一致，区别仅在于预取和缺失预测器的区别。因此可认为这两篇论文中共同提出的SRAM缓存结构是一个经过验证的元数据缓存结构，适合作为本文的基线模型结构。

但是在这两个原始工作中，额外的SRAM大小分别约为47KB与64KB，导致其命中率很差。由于FuseLLC的额外开销为125KB，因此本文在基线模型中将额外SRAM增加到了128KB至4MB不等，以充分地比较本文的工作获得的等效额外空间容量。

同时，这两个工作中都大量地使用了预取技术以及缺失预测器以提升其性能表现，但是这会导致难以分辨性能提升究竟是来自于预测器和预取器，还是来自于元数据缓存所带来的提升。因此进行实验时在基线模型中去掉了其预测器和预取器，只保留了SRAM缓存的部分。


\textbf{测试用例}

本文在测试时选用了SPEC CPU 2017测试套件中性能负载较高的子项作为测试用例，测试中的一些子项内存占用超过了快内存的容量，如557.xz\_r子项使用了5.8GB的内存容量，而549.fotonik3d\_r使用了13.4GB的内存容量，因而这些负载较为适合用于混合内存系统的性能测试。SPEC各子项的负载工作在RATE模式，即在多核上运行相同的副本。在模拟时先让模拟器快进（fast forward）前50亿至500亿条指令，使得各负载完成自己的初始化过程，随后在模拟器中运行接下来的50亿条指令。

\subsection{实验结果}

\textbf{整体性能表现}

本文以额外引入128KB SRAM作为DC元数据缓存的基线模型作为参考性能，然后分别比较了额外引入256KB至4MB大小的SRAM的基线模型的性能，以及本文设计的的FuseLLC的性能，以评估FuseLLC等效性能。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_8C_perform}
    \bicaption{\enspace FuseLLC性能测试}{\enspace 
    FuseLLC Performance Test}
    \label{fig:FuseLLC_8C_perform}
\end{figure}


测试结果如图\ref{fig:FuseLLC_8C_perform}所示。从整体性能来看，FuseLLC以大约125KB的额外开销，通过复用LLC空间，在性能上与引入额外3MB专用SRAM的性能表现大致相当。

\textbf{FuseLLC对缓存容量划分比例}


由于FuseLLC的设计核心思路是将LLC容量进行动态的划分，从而复用LLC的片上空间以加速DC元数据访问过程，因此有必要分析各负载中缓存的划分情况。

在测试过程中，FuseLLC每处理100万个请求将会统计并记录自身所有数据存储中LLC数据与DC元数据的占比。当测试点运行完毕后，会通过先前的记录，计算出该测试点下平均的元数据占用量（以MByte计）。测试的结果如图\ref{fig:FuseLLC_metasize}所示。

从结果可以看出，各测试点中元数据占据的容量围绕在3MB左右，但是在一些测试点，如525.x264\_r与500.perlbench\_r内，元数据占比显著少于其他测试点。测试结果表明FuseLLC可以根据各负载的不同性质而调整缓存划分的比例，从而在不同负载中获取良好的性能表现。


\begin{figure}[H]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_metasize}
    \bicaption{\enspace FuseLLC测试点中平均元数据容量}{\enspace 
    Average Metadata Capacity in FuseLLC}
    \label{fig:FuseLLC_metasize}
\end{figure}


\textbf{FuseLLC对LLC与DC元数据命中率的影响}

FuseLLC本质上是牺牲部分LLC的空间用于缓存DC元数据的数据，也就是牺牲了LLC的命中率以提升DC元数据的命中率。因此需要对LLC的命中率与DC元数据命中率进行分析。本文以额外引入128KB SRAM的基线模型作为参考，对比结果如图\ref{fig:FuseLLC_HitRate_LLC}与\ref{fig:FuseLLC_HitRate_Meta}所示。图中"128K SRAM LLC"与"FuseLLC LLC"分别代表基线模型与FuseLLC中LLC部分的命中率，"128K SRAM Meta"与"FuseLLC Meta"分别代表基线模型与FuseLLC中的DC元数据命中率。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{FuseLLC_HitRate_LLC}
    \bicaption{\enspace FuseLLC对LLC命中率的影响}{\enspace 
    The Impact of FuseLLC on LLC Hit Rate}
    \label{fig:FuseLLC_HitRate_LLC}
\end{figure}


\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{FuseLLC_HitRate_Meta}
    \bicaption{\enspace FuseLLC对元数据命中率的影响}{\enspace 
    The Impact of FuseLLC on Metadata Hit Rate}
    \label{fig:FuseLLC_HitRate_Meta}
\end{figure}

与额外增加128KB SRAM的基线模型对比，LLC的命中率略有下降，但是DC元数据命中率都有提升。以526.blender\_r子项为例，其LLC命中率下降了2.57\%，但是获得了23.75\%的元数据命中率提升。在所有测试点中，平均以1.63\%的LLC命中率下降换取了额外17.01\%的元数据命中率上升。在大部分测试子项中，元数据部分的命中率达到甚至超过了90\%。

通过对元数据命中率的分析可以看出，通过引入FuseLLC的设计，DC元数据访问开销大的问题得到了极大的缓解，大部分的DC元数据访问均可在FuseLLC中命中。



\textbf{局部争抢避让机制对性能的影响}



FuseLLC设计的核心机制之一是局部争抢避让机制，该机制允许存放着DC元数据的行交换到其他LLC组中，从而避让LLC的热点，减少LLC与DC元数据冲突产生的性能损失。

\begin{figure}[H]
    \centering
    \includegraphics[width=1\textwidth]{FuseLLC_SWAP_CMP}
    \bicaption{\enspace FuseLLC局部争抢避让机制对性能的影响}{\enspace 
    The Impact of FuseLLC's SWAP Mechanism on Performance}
    \label{fig:FuseLLC_SWAP_CMP}
\end{figure}

为了测试该机制对性能的影响，测试时在FuseLLC的基础上构建了一个用于对比的固定映射模型，该固定映射模型中，MPtrArray中的每一路数据根据路号固定地映射到LLC的某一个组中，由于此时不允许进行争抢避让操作，因此当LLC插入到存放着DC元数据的行中时，会将其直接换出。



测试结果如图\ref{fig:FuseLLC_SWAP_CMP}所示，柱状图数据代表引入了局部争抢避让机制对性能的提升，从图中可以看出，在多个对DRAM缓存性能敏感的测试子项上，该机制均能提升系统的性能。

\textbf{Major-Minor算法对命中率的影响}

在FuseLLC中，为了识别LLC的冷热区域以将DC元数据插入LLC的较冷区域是依赖于Major-Minor算法实现的，该算法主要影响的是LLC普通数据与DC元数据之间竞争时的数据摆放规则，进而影响其命中率。为了研究该算法对命中率的影响，本文在若干个对DC较为敏感的子项中进行了对比实验，以比较Major-Minor算法与LRU算法的表现差异，测试结果如表\ref{tab:major_minor_perform}所示。

从测试结果可以看出，Major-Minor算法会将DC元数据集中至LLC较冷的组中，导致LLC局部命中率轻微波动。但由于DC元数据避让了LLC的热点区域，使得DC元数据更少被LLC普通数据挤出，从而提升了DC元数据的生存周期进而提升其命中率。以520.omnetpp\_r子项为例，其LLC部分命中率下降了0.58\%，但是DC元数据部分命中率上涨了5.58\%。说明了Major-Minor算法比传统替换算法更适合于FuseLLC的应用场景。

\begin{table}[h]

    \bicaption{\enspace Major-Minor算法对命中率的影响}{\enspace 
    The Impact of the Major-Minor Algorithm on Hit Rate}
    \label{tab:major_minor_perform}
    \centering
    \resizebox{\textwidth}{!}{
        \begin{tabular}{ccccccc}
            \multicolumn{1}{l}{\textbf{}} & \multicolumn{1}{l}{\begin{tabular}[c]{@{}l@{}}MM LLC \\ Hit Rate\end{tabular}} & \multicolumn{1}{l}{\begin{tabular}[c]{@{}l@{}}LRU LLC \\ Hit Rate\end{tabular}} & \multicolumn{1}{l}{\begin{tabular}[c]{@{}l@{}}LLC \\ Delta\end{tabular}} & \multicolumn{1}{l}{\begin{tabular}[c]{@{}l@{}}MM Meta \\ Hit Rate\end{tabular}} & \multicolumn{1}{l}{\begin{tabular}[c]{@{}l@{}}LRU Meta \\ Hit Rate\end{tabular}} & \multicolumn{1}{l}{\begin{tabular}[c]{@{}l@{}}Meta \\ Delta\end{tabular}} \\ \hline
            507.cactuBSSN\_r              & 0.34\%                                                                         & 0.36\%                                                                          & -0.02\%                                                                  & 94.88\%                                                                         & 92.85\%                                                                          & 2.04\%                                                                    \\
            519.lbm\_r                    & 0.27\%                                                                         & 0.20\%                                                                          & 0.07\%                                                                   & 91.34\%                                                                         & 89.43\%                                                                          & 1.91\%                                                                    \\
            520.omnetpp\_r                & 10.27\%                                                                        & 10.85\%                                                                         & -0.58\%                                                                  & 79.32\%                                                                         & 73.74\%                                                                          & 5.58\%                                                                    \\
            521.wrf\_r                    & 9.16\%                                                                         & 9.92\%                                                                          & -0.76\%                                                                  & 95.28\%                                                                         & 93.40\%                                                                          & 1.88\%                                                                    \\
            526.blender\_r                & 11.56\%                                                                        & 11.94\%                                                                         & -0.38\%                                                                  & 96.98\%                                                                         & 95.61\%                                                                          & 1.37\%                                                                    \\
            549.fotonik3d\_r              & 0.37\%                                                                         & 0.60\%                                                                          & -0.23\%                                                                  & 83.18\%                                                                         & 81.25\%                                                                          & 1.93\%                                                                    \\
            557.xz\_r                     & 9.28\%                                                                         & 10.13\%                                                                         & -0.84\%                                                                  & 89.62\%                                                                         & 86.02\%                                                                          & 3.60\%                                                                   
            \end{tabular}
    }
    \end{table}
\section{小结}

本节提出了一种新型的混合末级缓存FuseLLC，旨在解决新型的DRAM缓存中元数据访问开销大的问题。本文创新性地引入了MPtrArray数据结构，配合多点采样算法，使得硬件可以高效地对LLC容量进行划分并管理，从而让系统能够复用LLC的空间以缓存DC元数据。同时，本文设计了识别LLC热点与冷点区域的Major-Minor算法，配合上局部争抢避让机制减少LLC部分的数据与DC元数据的冲突，从而提升系统性能。在多数测试中，FuseLLC在DC元数据缓存部分的命中率已经高达90\%，使得DC元数据访问开销大的问题得到缓解。虽然在测试时，测试系统基于DRAM缓存进行构建，但是该设计也同样适用于PoM类型的混合内存系统。


}
